// 第一题
// 搜索插入的位置
// // 给定一个顺序数组和一个目标值
// 1、在数组中找到目标值，并且返回其索引
// 2、如果目标值不存在数组中，返回它将被按顺序插入的位置索引

// 输入： [1, 3, 5, 6] 5
// 输出： 2

// 输入： [1, 3, 5, 6] 2
// 输出： 1

// 输入： [1, 3, 5, 6] 7
// 输出： 4



// 循环遍历数组
function searchInsertIndex(array, target) {
    for (let index = 0; index < array.length; index++) {
        const element = array[index];
        if (element >= target) {
            return index;
        }
    }
    return array.length;
}

let arr = [1, 3, 5, 6];
let res1 = searchInsertIndex(arr, 5) 
let res2 = searchInsertIndex(arr, 2) 
let res3 = searchInsertIndex(arr, 7) 
console.log(res1, res2, res3)



// 二分法查找
function searchInsertIndex2(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let mid = Math.floor((right - left) / 2);
    while(left <= right) {
        if (arr[mid] < target) {
            left = mid;
        } else if (arr[mid] > target) {
            right = mid;
        } else {
            return mid;
        };
        mid = Math.floor((right - left) / 2);
    }
    return arr.length;
}

let arr2 = [1, 3, 5, 6];
let res4 = searchInsertIndex(arr2, 5) 
let res5 = searchInsertIndex(arr2, 2) 
let res6 = searchInsertIndex(arr2, 7) 
console.log(res4, res5, res6)





